/* ------------------------------------------------------------ */
/*                       file information                       */
/* ------------------------------------------------------------ */

// Filename:  x3mem.h
// Purpose:   Memory management
// License:   MIT/X. (c) OldCoder (Robert Kiraly) 1987-2022.

/* ------------------------------------------------------------ */
/*                      header file setup                       */
/* ------------------------------------------------------------ */

#ifndef _X3MEM_H                /* skip this file if loaded     */
#define _X3MEM_H 1              /* flag this file               */

#include "deps.h"
#include "eprintf.h"

/* ------------------------------------------------------------ */
/*                        basic definitions                     */
/* ------------------------------------------------------------ */

#ifndef x3u_int
#define x3u_int     unsigned int
#endif

#ifndef x3u_long
#define x3u_long    unsigned long
#endif

#ifndef V_OBJ
#define V_OBJ       void
#endif

/* ------------------------------------------------------------ */
/*                   X3MEM package - overview                   */
/* ------------------------------------------------------------ */

/* The  X3MEM package includes the public functions listed  be- */
/* low. For more information, see the functions themselves.     */

/* ------------------------------------------------------------ */

/* QLIST support functions:                (*) = macro function */

/*      1. chk_qm0()   -- checks a "qmalloc()" storage pointer  */
/*      2. chk_qma()   -- checks an entire QLIST                */
/* (*)  3. chk_qmp()   -- generic version of "chk_qm0()"        */
/*      4. qcalloc()   -- allocates and clears memory           */
/*      5. qmalloc()   -- allocates memory                      */
/*      6. qrealloc()  -- re-allocates memory                   */
/*      7. qfree()     -- frees allocated memory                */
/*      8. qflush()    -- frees an entire QLIST                 */
/*      9. sys_mem()   -- returns amount of free system memory  */
/* (*) 10. xqfree()    -- generic version of "qfree()"          */

/* ------------------------------------------------------------ */

/* Simplified QLIST interface layer:                            */

/*     11. sqCalloc()  -- similar to "calloc()"                 */
/*     12. sqChkHeap() -- checks the entire "sq..." heap        */
/*     13. sqChkPtr()  -- checks an "sq..." storage pointer     */
/*     14. sqFlush()   -- frees all "sq..." storage             */
/*     15. sqFree()    -- frees one "sq..." storage block       */
/*     16. sqMalloc()  -- similar to "malloc()"                 */
/*     17. sqRealloc() -- similar to "realloc()"                */

/* ------------------------------------------------------------ */
/*                 QLIST pointers - explanation                 */
/* ------------------------------------------------------------ */

/* The  X3MEM functions support multiple  dynamic-memory  allo- */
/* cation  lists.   The  "qmalloc()"  function,   for  example, */
/* allocates memory from a  specified allocation list,  and the */
/* "qfree()" function returns memory to the associated list.    */

/* Multiple-allocation  lists  provide   greater  control  over */
/* memory allocation;  e.g., the caller can free up one list in */
/* its entirety without disturbing other lists.                 */

/* Additionally,  the  use of  multiple  allocation  lists  can */
/* reduce the  fragmentation problems which  occur on  virtual- */
/* memory systems when free lists have grown large.             */

/* Allocation lists are specified by  QLIST pointers; to create */
/* a new allocation list, the user simply defines a new (empty) */
/* QLIST structure.                                             */

/* If a program does not require multiple allocation lists, the */
/* predefined general-purpose list "QM_GEN" may be used.        */

/* ------------------------------------------------------------ */
/*                 QMALLOC structure definitions                */
/* ------------------------------------------------------------ */

/* alignment data type          */

#ifdef QMSA                     /* stand-alone version          */
#ifndef DEF_ALIGN               /* set default alignment type   */
#define DEF_ALIGN   unsigned int
#endif
#endif                          /* endif "QMSA"                 */

#ifdef DEF_ALIGN                /* is alignment type defined?   */
typedef DEF_ALIGN QM_ALIGN;     /* use specified alignment type */
#else                           /* use default   alignment type */
typedef long QM_ALIGN;          /* "long-integer" alignment     */
#endif                          /* endif DEF_ALIGN              */

                                /* size of an alignment unit    */
#define QMASIZE     (sizeof(QM_ALIGN))

/* ------------------------------------------------------------ */

/* "size" data type             */

#define QM_SIZE_T       unsigned int

/* ------------------------------------------------------------ */

/* QMALLOC memory block header  */

union qm_header
{
    QM_ALIGN qm_d;              /* align the block header       */

    struct                      /* begin header proper (qm_h)   */
    {
        union                   /* begin multi-use portion      */
        {                       /* see explanation below        */
            union qm_header *n0_free;
            struct qlist *q0_owner;
        }
            qm_x;               /* end   multi-use portion      */

        QM_SIZE_T q0_chk;       /* consistency-check value      */
        QM_SIZE_T q0_size;      /* block size                   */
    }
        qm_h;                   /* end   header proper (qm_h)   */
};

typedef union qm_header QM_HDR; /* typedef the block header     */

/* ------------------------------------------------------------ */

/* simplify the structure       */

#define nxt_free    qm_h.qm_x.n0_free
#define qa_size     qm_h.q0_size
#define qm_chk      qm_h.q0_chk
#define qm_owner    qm_h.qm_x.q0_owner

/* ------------------------------------------------------------ */

/* QM_HDR structure             */

/* The  "QM_HDR" structure defines a  block of  dynamic memory. */
/* The block  is aligned on a  "QM_ALIGN" boundary,  and begins */
/* with a header of type  "QM_HDR".  The  rest of the block  is */
/* used for storage.                                            */

/* "qa_size" is the  total size of the memory block  (including */
/* the header itself)  in  "QM_ALIGN"  alignment  units  (i.e., */
/* units of QMASIZE bytes).                                     */

/* "nxt_free"  and  "qm_owner" are  context-dependent.  See the */
/* discussion  of the  QLIST  structure  below  for  additional */
/* information.                                                 */

/* "qm_chk" is used internally for consistency checking.        */

/* ------------------------------------------------------------ */

/* QLIST structure              */

struct qlist
{
    QM_HDR *qm_free;            /* QLIST free list              */
    QM_HDR *qm_sysmem;          /* QLIST system-memory list     */
    QM_SIZE_T qm_block;         /* allocation blocking factor   */
    char qm_nofree;             /* non-freeable flag            */
};

typedef struct qlist QLIST;     /* typedef the list header      */
                                /* null structure pointer       */
#define NULL_QLS    ((QLIST *) ZERO)

/* ------------------------------------------------------------ */

/* QLIST free-list              */

/* The  "qm_free" field for a  QLIST points to a  list of  free */
/* memory blocks  associated  with the  QLIST.  Each free block */
/* begins with a  "QM_HDR" block header.  The  free blocks  are */
/* linked  together by the  "nxt_free"  field  in the  "QM_HDR" */
/* header.  Blocks are allocated from this  list by "qmalloc()" */
/* and freed onto the list by "qfree()".                        */

/* When  "qmalloc()" allocates  a  block from a  free-list,  it */
/* points the  "qm_owner" field in the header to the QLIST from */
/* which  the block  was  obtained.  "qfree()" uses this  field */
/* subsequently when the block is freed.                        */

/* The  memory blocks in the  free list are  carved  out  of  a */
/* lower-level  system memory chain,  which is discussed in the */
/* next section.                                                */

/* ------------------------------------------------------------ */

/* QLIST system-memory list     */

/* The  "qm_sysmem" field for a  QLIST points to a list of low- */
/* level  "system  memory"  blocks associated with  the  QLIST. */
/* Each system memory block begins with a "QM_HDR"  block head- */
/* er.  The  system  memory blocks are  linked together  by the */
/* "nxt_free" field in the "QM_HDR" header.                     */

/* This  linked  list  contains  all  of  the  dynamic  storage */
/* currently associated  with a  QLIST  (on the  "qm_free" free */
/* list or not).  The blocks in this list are obtained from the */
/* operating system.                                            */

/* "qmalloc()" carves the storage portion of each system memory */
/* block up into  sub-blocks,  writes "QM_HDR" headers onto the */
/* sub-blocks,  and  uses  these  secondary  headers  to  build */
/* higher-level (qm_free) allocation lists.                     */

/* ------------------------------------------------------------ */

/* allocation blocking factor   */

/* The "malloc"-based version of "qmalloc()" uses  the standard */
/* library routine "malloc()" to allocate dynamic memory at the */
/* system level.                                                */

/* The  "stand-alone" version of "qmalloc()" uses  an  internal */
/* utility  routine to  allocate dynamic memory  at  the system */
/* level.                                                       */

/* The "qm_block" field in a QLIST header specifies the minimum */
/* amount of memory  (in bytes)  to be  requested for the QLIST */
/* per system-level memory allocation call.                     */

/* If the  "qm_block" field is  not set,  a reasonable  default */
/* value is used.                                               */

/* If the host system has  virtual memory,  setting  "qm_block" */
/* as follows may improve performance:                          */
/*                                                              */
/* qm_block <- system memory page size minus  total size of all */
/*             system-level storage headers.                    */

/* ------------------------------------------------------------ */
/*                    misc. global variables                    */
/* ------------------------------------------------------------ */

/* "QM_GEN" is intended for use as a general-purpose QLIST.     */

/* Note:  Since "QM_GEN[]" is an array, "QM_GEN" serves both as */
/* a QLIST pointer and as the QLIST entry itself.               */

UX3_EXT QLIST QM_GEN [ONE];     /* general-purpose QLIST        */
UX3_EXT QLIST QM_LZ  [ONE];

/* ------------------------------------------------------------ */

/* "qm_retsys" is a flag used by the  "qflush()" function.  See */
/* "qflush()" for additional information.                       */

UX3_EXT char qm_retsys;         /* "qflush()" flag              */

/* ------------------------------------------------------------ */
/*                        macro functions                       */
/* ------------------------------------------------------------ */

/* "chk_qmp(xp)"  checks the  pointer "xp" and  terminates  the */
/* caller  with  an  error  message  if  "xp" is  not  a  valid */
/* "qmalloc()"  storage pointer.  "xp" may be a pointer of  any */
/* type; "chk_qmp()" typecasts the pointer appropriately.       */

/* Note:  A  valid  storage  pointer  becomes  invalid  if  the */
/* associated storage is freed.                                 */

/* "chk_qmp()"  is a  macro  interface to  the  function  "chk_ */
/* qm0()".  See the  description of  "chk_qm0()" for additional */
/* information.                                                 */

/* ------------------------------------------------------------ */

#define chk_qmp(xp)     chk_qm0 ((V_OBJ *) (xp))

/* ------------------------------------------------------------ */

/* The macro function "xqfree()" is equivalent to the non-macro */
/* function  "qfree()",  with the  distinction that  "xqfree()" */
/* typecasts its argument  appropriately.  See the  description */
/* of "qfree()" for additional information.                     */

/* ------------------------------------------------------------ */

#define xqfree(p)       qfree ((V_OBJ *) (p))

/* ------------------------------------------------------------ */
/*                  X3MEM function prototypes                   */
/* ------------------------------------------------------------ */

V_PROTO   chk_qm0   (argp1 (V_OBJ *));
V_PROTO   chk_qma   (argp1 (QLIST *));
V_OBJ    *qcalloc   (argp3 (QLIST *,x3u_int,x3u_int));
V_PROTO   qflush    (argp1 (QLIST *));
V_PROTO   qfree     (argp1 (V_OBJ *));
V_OBJ    *qmalloc   (argp2 (QLIST *,int));
V_OBJ    *qrealloc  (argp2 (V_OBJ *,int));
long      sys_mem   (argp0 ());

/* ------------------------------------------------------------ */

V_OBJ    *sqCalloc  (argp2 (x3u_int, x3u_int));
V_PROTO   sqChkHeap (argp0 ());
V_PROTO   sqChkPtr  (argp2 (V_OBJ *, char *));
V_PROTO   sqFlush   (argp0 ());
V_PROTO   sqFree    (argp1 (V_OBJ *));
V_OBJ    *sqMalloc  (argp1 (x3u_int));
V_OBJ    *sqRealloc (argp2 (V_OBJ *, x3u_int));

/* ------------------------------------------------------------ */
/*                          wrap it up                          */
/* ------------------------------------------------------------ */

#endif                          /* endif _X3MEM_H               */
